package org.example.leetcpde;

import org.junit.jupiter.api.Test;

public class longestCommonPrefix {

    @Test
    void aa() {
        String[] strs = {"flower","flower","flower","flower"};
        String s = longestCommonPrefix(strs);
        System.out.println(s);

    }

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        int length = strs.length;
        return longestCommonPrefix(strs, 0, length - 1);
    }

    String longestCommonPrefix(String[] strs,
                               int left,
                               int right) {
        if (left == right) {
            return strs[left];
        }

        int mid = (left + right) >> 1;
        String l = longestCommonPrefix(strs, left, mid);
        String r = longestCommonPrefix(strs, mid + 1, right);
        return longestCommonPrefix(l, r);
    }

    String longestCommonPrefix(String a,
                               String b) {
        char[] chars = a.toCharArray();
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            if (i >= b.length() || a.charAt(i) != b.charAt(i)) {
                break;
            }

            builder.append(a.charAt(i));
        }

        return builder.toString();
    }
}